import java.util.ArrayList;
import java.util.List;
//给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
//
//注意：请不要在超过该数组长度的位置写入元素。
//请对输入的数组就地进行上述修改，不要从函数返回任何东西。
//
//示例 1：
//输入：arr = [1,0,2,3,0,4,5,0]
//输出：[1,0,0,2,3,0,0,4]
//解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
//示例 2：
//
//输入：arr = [1,2,3]
//输出：[1,2,3]
//解释：调用函数后，输入的数组将被修改为：[1,2,3]

//解法一：直接创建一个顺序表来存储，按逻辑存完数据后，再存回去
//空间复杂度太大不推荐O(arr.length)
public class Solution {
    public void duplicateZeros(int[] arr) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                list.add(0);
                list.add(0);
            }else {
                list.add(arr[i]);
            }
        }
        for (int j =0;j<arr.length; j++) {
            arr[j] = list.get(j);
        }
    }
}

//解法二：力扣：复写零  1089
//通过双指针来模拟栈，但是并没有实际开辟一个栈，因此只花费了常数个内存空间
//空间复杂度为O(1)
public class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int top = 0;//top为个数而不是栈的下标
        int i = -1;
        while (top < n) {
            i++;
            if (arr[i] != 0) {
                top++;
            } else {
                top += 2;
            }
        }
        int j = n - 1;//模拟尾部下标
        if (top == n + 1) {
            arr[j] = 0;
            j--;
            i--;
        }
        while (j >= 0) {
            arr[j] = arr[i];
            j--;
            if (arr[i] == 0) {
                arr[j] = arr[i];
                j--;//如果为零要额外赋值一次
            }
            i--;
        }
    }
}

